package num05;

/**
 * 题目：5. 最长回文子串
 * <p>
 * 朴素算法
 * 首先枚举回文串的中心 i，然后分两种情况向两边扩展边界，直到达到边界或者不满足回文串定义为止：
 * 回文串长度是奇数，则依次判断 s[i − k] == s[i + k], k = 1,2,3…
 * 回文串长度是偶数，则依次判断 s[i − k] == s[i + k − 1], k = 1,2,3…
 */
class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();


        System.out.println(solution.longestPalindrome("abca"));
    }


    public String longestPalindrome(String s) {
        String ans = "";
        for (int i = 0; i < s.length(); i++) {

            // 回文串为奇数
            int l = i - 1, r = i + 1;
            String sub = getString(s, l, r);
            if (sub.length() > ans.length()) {
                ans = sub;
            }

            // 回文串为偶数
            l = i - 1;
            r = i + 1 - 1;
            sub = getString(s, l, r);
            if (sub.length() > ans.length()) {
                ans = sub;
            }
        }
        return ans;
    }


    /**
     * 返回回文串
     */
    String getString(String s, int l, int r) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            l--;
            r++;
        }

        return s.substring(l + 1, r);
    }
}